package sort.impl;

import sort.BaseSort;

public class HeapSort implements BaseSort {
    @Override
    public void safeSort(Comparable[] arr) {
        int heapSize = arr.length;
        buildHeap(arr);
        while (heapSize > 1){
            BaseSort.swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
        }
    }

    void heapify(Comparable[] arr, int i, int n){
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int maxIndex = i;
        if(leftChild < n && arr[leftChild].compareTo(arr[maxIndex]) > 0){
            maxIndex = leftChild;
        }
        if(rightChild < n && arr[rightChild].compareTo(arr[maxIndex]) > 0){
            maxIndex = rightChild;
        }
        if(maxIndex != i){
            BaseSort.swap(arr, maxIndex, i);
            heapify(arr, maxIndex, n);
        }
    }

    void buildHeap(Comparable[] arr){
        int len = arr.length;
        int heapSiez = len;
        for(int i = heapSiez / 2 - 1; i >= 0; i--){
            heapify(arr, i, heapSiez);
        }
    }
}
